leetcode 第一题 Two Sum

这是 leetcode 上算法的第一题,官方定位为简单题目,事实也是如此。题目地址

题目:给定一个整数数组,返回两个数字的返回索引,这样它们就可以添加到特定的目标。假设每个输入都只有一个结果,不会两次使用相同的元素。例如:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解法一


1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 最简单的双重循环
var twoSum = function(nums, target) {
var d ={};
var result = [];
for (var i = 0; i < nums.length; i++) {
for (var j = 0; j < nums.length; j++) {
if (nums[i] + nums[j] === target && i !== j) {
(i < j) ? result.push(i, j) : result.push(j, i);
return result;
}
}
}
return result;
};

基本所有人都会,但是该方法算法复杂度为O(n2),运行时间过长(246ms)

解法二


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var twoSum = function(nums, target) {
var d ={};
var result = [];
for (var i = 0; i < nums.length; i++) {
var a = target - nums[i] +'';
var t = {};
d[a] = i;
}
for (var b = 0; b < nums.length; b++) {
var c = nums[b]+'';
if(d[c] !== undefined){
var x = d[c], y = nums.indexOf(nums[b]);
if (x !== y){
(y < x) ? result.push(y, x) : result.push(x, y);
return result;
}
}
}
return result;
};

这种解法是用两个单独的循环,所以运行时间大大减少(116ms)。

大概思路是先做一遍遍历,将数据以’目标值减去数组中的某个值 : 该值的索引’这样类似map的方式存储在对象d中,然后再做一次遍历根据是否是新对象的属性来判断有没有解。 这个解法是我对这道题目的思考过程,中间有很多多余的操作。

解法三


1
2
3
4
5
6
7
8
9
10
11
12
13
var twoSum = function(nums, target) {
var ans = [];
var exist = {};
for (var i = 0; i < nums.length; i++){
if (typeof(exist[target-nums[i]]) !== 'undefined'){
ans.push(exist[target-nums[i]]);
ans.push(i);
}
exist[nums[i]] = i;
}
return ans;
};

leetcode 上大佬的解法,运行时间(92ms),直接在一个循环中解决问题。

大致思路,就是遍历数组,在exis对象中存入’值’:’索引’的属性,使用typeof 判断是否有符合条件的属性,有的话存入ans,最后返回ans。

对于这个算法我本来想在ans.push(i)后加个 return ans,想这样不用把算法走完或许会再少点时间,但是时间反而多了一点。然后我又尝试用break,好像是减少了几ms,但是leetcode运行同样的算法时间都有变化,这个就算在误差内了。

这道题目虽然不是很难,但是加深了我对javascript基础的认知,也感受到了用javascript写算法与java这种面向对象语言的区别。